package com.example.algorithm.huawei_rongyao_29;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// 在数组中找到出现次数大于n/k的数
// 简单
/**
 * 标题：在数组中找到出现次数大于n/k的数 | 时间限制：2秒 | 内存限制：262144K
 * 给定一个整型数组arr，再给定一个整数k，打印所有出现次数大于n/k的数，如果没有这样的数,请打印”-1“。
 * 输入描述:
 * 输入包含两行，第一行输入包含两个整数n和k,第二行包含n个整数，代表数组arr。
 * 输出描述:
 * 输出所有出现次数大于n/k的数，如果没有这样的数,请输出”-1“。
 * <p>
 * 要解决这个问题，可以使用哈希表来统计数组中每个数字的出现次数，然后再遍历哈希表，找出出现次数大于 n/k 的数字。
 */
public class Q06_FindMajorityElements {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String inputLine1 = scanner.nextLine();
        int[] numbers = Utils.scannerAndTransIntoInt(inputLine1);
        int n = numbers[0]; // 数组长度
        int k = numbers[1]; // 给定的整数k

        String inputLine2 = scanner.nextLine();
        int[] numbers2 = Utils.scannerAndTransIntoInt(inputLine2);

        findElements(numbers2, k);

        scanner.close();
    }

    public static void findElements(int[] arr, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            // 单独用map来计数。键是元素本身，值是元素出现的总次数
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int threshold = arr.length / k;
        boolean found = false;

        // 遍历map
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > threshold) {
                System.out.print(entry.getKey() + " ");
                found = true;
            }
        }
        if (!found) {
            System.out.println("-1");
        }
    }
}

